home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 15682 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: prairienet.org!wemccaug
  2. From: wemccaug@prairienet.org (Wendy E. McCaughrin)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Search routines
  5. Date: 21 Apr 1996 03:31:53 GMT
  6. Organization: University of Illinois at Urbana
  7. Message-ID: <4lca79$f86@vixen.cso.uiuc.edu>
  8. References: <3179B683.4722@neosoft.com> <31741C46.2DF2@stc.net>
  9. Reply-To: wemccaug@prairienet.org (Wendy E. McCaughrin)
  10. NNTP-Posting-Host: firefly.prairienet.org
  11.  
  12.  
  13. In a previous article, laxrl@neosoft.com (Reuven Lax) says:
  14.  
  15. >dmaher@stc.net wrote:
  16. >> 
  17. >
  18. >  I am searching for
  19. >> information on search routines.  I need at least five, and I was
  20. >> wondering if anybody could help me out.  I'm aware of binary and
  21. >> sequential searches for C++, but I really need at least 3 or 4 more.
  22. >
  23. >Well, you have the Boyer-Moore algorithm, and the Knuth-Morris-Prat (a 
  24. >mouthfull) algorithm, for unordered dsts structures.  Binary search is 
  25. >for ordered data structers.  If you build a b-tree out od your data that 
  26. >also signficately improves your search speed.  Another popular method, 
  27. >is hashing.  You might want to look some of these up (that is if your 
  28. >not familiar with any of them).
  29. >
  30. >Reuven Lax
  31.  
  32.  The KMP and BM algorithms are string-matching algorithms, not
  33.  general search schemes. For an excellent rendition on these and other
  34.  pattern-matching approaches, you should read Bruce Watson's Ph.D.
  35.  dissertation, available from (I believe) University of Amsterdam, the
  36.  Netherlands.
  37.  
  38.  However, the mistake is understandable, given the generality of
  39.  searching as an activity in general (w.v., Knuth, Vol. III). In fact,
  40.  I suppose BM and KMP can be regarded as searches in the simplest kind
  41.  of data-structure, the chracter-vector 'string'. Binary and sequential
  42.  searches occur in the next level up: the string-vector of "names".
  43.  
  44. Hashing isn't really a search method (which is why Knuth discusses it in
  45.  Vol. II, not Vol. III) but is instead an indexing method.
  46.  
  47. Search strategies are often characterized by the data-structures they
  48.  get applied to, most notably, trees. Thus level-order (also called
  49. "breadth-first order") and depth-first order search apply to acyclic
  50.  graphs connected graphs (trees).
  51.  
  52. wem
  53.  
  54.